Many applications require a one-to-many content distribution, where one computer in a computer network sends content to several other computers on the network. An example of such applications includes software distribution, Internet TV/video streaming, video conferencing, personal media distribution, and peer-to-peer (P2P) web content duplication. A P2P network is a type of network in which each computer has equivalent capabilities and responsibilities.
FIG. 1 is a block diagram illustrating the one-to-many content distribution problem. The network 100 includes a source node s, which holds the content to be distributed, and multiple peer nodes ti, i=1, 2, . . . , N, each of which may or may not request a copy of the content. Both the source node and the peer nodes are end-user nodes. They are usually computers connected to the Internet through an internet service provider (ISP), using an asymmetric digital subscriber line (ADSL), cable modem, campus, or corporate network link. The simplest approach for a source node to distribute content in the setting shown in FIG. 1 is to allow the source node send the content directly to the destination nodes. Though straightforward, the throughput of the content distribution is bounded by the upload bandwidth of the source node, which is usually fairly limited.
One network-level solution to address such a content distribution problem as shown in FIG. 1 is Internet Protocol (IP) multicast. In IP multicast, a single packet that is transmitted from a source is duplicated at routers along a distribution tree rooted at the source. In this manner, content is delivered to an arbitrary number of receivers. Although IP multicast is an efficient solution, its deployment has been slow in the real world because of issues and problems such as inter-domain routing protocols, Internet Service Provider (ISP) business models, congestion control along the distribution tree, and so forth. Because of these problems in deploying a network-level multicast service, the vast majority of traffic in the Internet today is unicast based, whereby two computers directly talk to each other.
Since a network-level solution is not generally feasible for the reasons given, a variety of different approaches have been developed to enable P2P computers, instead of routers, distribute the content from the source. In general, the most promising approach is application-level multicast (ALM). In ALM, a multicast distribution tree is formed and overlaid on an existing network. Instead of using the multicast protocol, each peer computer in the distribution tree uses a unicast protocol to implement all multicast related functionalities including packet replication, membership management and content delivery on the overlaid network.
Some examples of ALM systems include Scattercast, which is described in a paper by Y. Chawathe entitled “Scattercast: an architecture for internet broadcast distribution as an infrastructure service”, a PhD thesis for the University of California, Berkeley, August 2000, and Overcast, which is described in a paper by J. Jannotti, D. K. Gifford, K. L. Johnson, M. F. Kaashoek, and J. W. O'Toole Jr. entitled “Overcast: reliable multicasting with an overlay network” in Proc. of the Fourth Symposium on Operating System Design and Implementation (OSDI), October 2000. Both Scattercast and Overcast use a single tree to distribute content.
FIG. 2 is a block diagram illustrating the content distribution techniques using a single distribution tree 200, as is used in Scattercast and Overcast. In this configuration, a source node, s, sends data to node t1, which forwards the data to nodes t2 and t3. The ALM distribution tree 200 utilizes the upload bandwidth of the intermediate node t1, whereas the upload bandwidths of the leaf nodes t2 and t3 are not utilized. Compared with letting the source node directly send its content to all other clients, the distribution tree approach shown in FIG. 2 reduces the network load of the source, and thus achieves a more efficient content distribution.
One problem, however, with Scattercast and Overcast is that they are inefficient at distributing content. Specifically, in a distribution tree, the intermediate nodes redistribute the content, while the leaf nodes only receive the content. This means that the upload bandwidths of the leaf nodes are not utilized for content distribution.
Several attempts have been made to overcome such inefficiency. These techniques include a technique called CoopNet, which is described in papers by V. N. Padmanabhan and K. Sripanidkulchai entitled “The Case for Cooperative Networking”, in Proc. of the First Intemational Workshop on Peer-to-Peer Systems (IPTPS), Cambridge, Mass., USA, March 2002, and by V. N. Padmanabhan, H. J. Wang, and P. A. Chou, “Resilient Peer-to-Peer Streaming,” in Proc. IEEE International Conference on Network Protocols (ICNP), Atlanta, Ga., USA, November 2003; and a technique called SplitStream, which is described in a paper by M. Castro, P. Druschel, A-M. Kermarrec, A. Nandi, A. Rowstron and A. Singh entitled “SplitStream: High-bandwidth content distribution in a cooperative environment”, in Proc. of the International Workshop on Peer-to-Peer-to-Systems, Berkeley, Calif., February, 2003. Each of these techniques split the content into multiple stripes and distributed the stripes across separate multicast trees with disjoint interior nodes. Any peer computer can be an interior node in one of the multicast trees, and can contribute to forwarding the content.
CoopNet uses a centralized tree management scheme, while SplitStream relies on Pastry to maintain the distribution tree. Pastry is described in a paper by A. Rowstron and P. Druschel entitled “Pastry: scalable, distributed object location and routing for large-scale peer-to-peer systems” in Proc. of IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, pages 329-350, November, 2001. CoopNet further utilizes multiple description coding (MDC) and forward error correction (FEC) to protect from packet loss and node failure.
FIG. 3 is a block diagram illustrating a two application-level multicast tree configuration 300, as is used on CoopNet and SplitStream. The content is divided into two equal stripes. A first stripe 310 is sent to node t1, which forwards the stripe to nodes t2 and t3. A second stripe 320 is sent to node t2, which forwards the strip to nodes t1 and t3. It should be noted that in FIG. 3 the distribution route of the first stripe is marked with a solid line, and the distribution route of the second stripe with a dashed line. This means that the contents delivered on these links is different. One problem with this configuration is that the system 300 utilizes the upload bandwidths of nodes t1 and t2, but fails to utilize the upload bandwidth of node t3, thus reducing efficiency.
Other techniques that attempted to overcome such inefficiency include a technique called FastReplica, discussed in paper by L. Cherkasova and J. Lee entitled “FastReplica: Efficient Large File Distribution within Content Delivery Networks” in Proc. of the 4-th USENIX Symposium on Internet Technologies and Systems, Seattle, Wash., Mar. 26-28, 2003, and a technique called Bullet, discussed in a paper by D. Kostic, A. Rodriguez, J. Albrecht, A. Vahdat entitled “Bullet: High Bandwidth Data Dissemination Using an Overlay Mesh” in Proc. 19th ACM Symposium on Operating Systems Principles, Oct. 19-22, 2003, the Sagamore, N.Y. Both of these techniques investigated the issue of efficient and reliable replication of large files. If there were n nodes, FastReplica first partitioned the file into n subfiles of equal size. Each subfile was then transferred to a different peer in the group, which was subsequently replicated and transferred to the other peers. In Bullet, peer nodes were organized into an overlay tree. Each node split the content received from the parent into a disjoint set of blocks, with each set sent to a different child node. The child nodes then discovered the missing blocks and the nodes that held the missing blocks, and sent requests to recover the missing blocks.
Looking closer at the FastReplica technique, it should be noted that this technique is specifically designed for file download. For an N node P2P network, FastReplica distributes the file with N height-2 multicast trees with intermediate degree N-1. FIG. 4 is a block diagram illustrating a sample FastReplica configuration 400 of three peer nodes. FastReplica distributes the file in two steps: the distribution step and the collection step. In the distribution step, the file is split into three subfiles and sent to nodes t1, t2 and t3 (along solid, dashed, and dotted lines), respectively. In particular, the three subfiles are sent along first stripe 410, a second stripe 420, and a third stripe 430. After the distribution step, the collection step is implemented. Each peer node forwards its subfile to the other peer nodes. As shown in FIG. 4, each of the peer nodes is engaged in the content distribution in FastReplica.
A practical P2P content distribution system has been implemented using a technique called BitTorrent. BitTorrent is described in a paper by B. Cohen that is entitled “Incentives build robustness in BitTorrent” and is available at the web site http://bitconjurer.org/BitTorrent/bittorrentecon.pdf. BitTorrent includes sharing incentive so that peers are willing to distribute content because the more content they upload, the more they will be able to download from the peers. These are just a few examples of the many recent schemes for application-level multicast.
Although the above ALM distribution strategies are more efficient than directly sending content from the source to the peers, they fail to achieve the most efficient content distribution in the network. Specifically, none of the above techniques has adequately considered the differences in bandwidth between the peer nodes. Each technique also fails to fully engage the bandwidth resources of all the peer nodes to distribute the content.
All of the above one-to-many content distribution approaches discussed above adapt to the capabilities of the peer nodes (the upload/download bandwidths of the peer nodes) by establishing a suitable network topology. Nodes with high bandwidth are placed in the center of the distribution network, and are in charge of more content distribution. Once the network topology is established, the content is distributed in fixed stripes through the established network. The problem with these distribution strategies is that the distribution network is less flexible to adapt to changes in the network conditions (such as any congestion of certain nodes/links). This can severely reduce efficiency of the content distribution. Therefore, what is needed is a one-to-many content distribution technique that distributes content in a most efficient manner possible in order to realize the maximum potential from the computer network.